package hyy_2022;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 由小写字母组成的字符串S
 * 重复项删除操作,选择两个相邻且相同的字符,并删除
 * 在S上反复执行重复项删除操作,直至无法继续删除
 *
 * abbaca -> ca
 */
public class _0815_1047_RemoveDuplicates {

    /**
     * 栈
     * 1、遍历字符串
     * 2、当前元素与栈顶相同,将栈顶元素删除;否则入栈
     * @param s
     * @return String
     */
    public String removeDuplicates(String s) {
        if(s == null || s.length() == 0) {
            return null;
        }
        Deque<Character> stack = new ArrayDeque<>();
        for(int i=0;i<s.length();i++) {
            //当前元素
            Character character = s.charAt(i);
            //栈顶元素
            Character top = stack.peek();
            if(top == null || !top.equals(character)) {
                stack.push(character);
            } else {
                stack.pop();
            }
        }
        String removeAfter = "";
        while(!stack.isEmpty()) {
            removeAfter = stack.pop() + removeAfter;
        }
        return removeAfter;
    }
}
